using System;
using System.Collections;
using System.Text;

namespace cuberga.Utils
{
public class Permutation {
        private int[] _data = null;  
        //private int _order = 0;      

        public int[] ToStructure {
            get {
                return _data;
            }
        }

        public override bool Equals(object obj) {
            if (!(obj is Permutation))
                return false;
            int[] another = ((Permutation)obj).ToStructure;
            
            if (another.Length != _data.Length)
                return false;

            for(int i = 0; i < _data.Length; i++)
                if (_data[i] != another[i])
                    return false;

            return true;
        }

        public override int GetHashCode() {
            return base.GetHashCode ();
        }

        private static System.Random r = new System.Random(unchecked((int)DateTime.Now.Ticks));
        //private static RNGCryptoServiceProvider r = new RNGCryptoServiceProvider();
        private void Shuffle(int n) {
            // Initialize source array
            ArrayList tmp = new ArrayList();
            for (int i = 0; i < n; i++) {
                tmp.Add(i);
            }

            // transfer source array to permutation
            _data = new int[n];
            //System.Threading.Thread.Sleep(1);
            for (int i = 0; i < n; i++) {
                int randomIndex = r.Next(tmp.Count);
                _data[i] = (int)tmp[randomIndex];
                tmp.RemoveAt(randomIndex);
            }
        }

        public Permutation(int n) {
            Shuffle(n);
        }

        public Permutation(int[] a) {
            _data = new int[a.Length];
            a.CopyTo(_data, 0);
        } 

        public bool IsValid() {
            bool[] checks = new bool[_data.Length];  

            for (int i = 0; i < _data.Length; ++i) {
                if (_data[i] < 0 || _data[i] >= _data.Length)
                    return false;  // value out of range

                if (checks[_data[i]] == true)
                    return false;  // duplicate value

                checks[_data[i]] = true; // mark as visited
            }
                
            return true;
        }  // IsValid()

        public Permutation Successor() {
            Permutation result = new Permutation(_data.Length);  

            int left, right;
                
            for (int k = 0; k < _data.Length; ++k) {  // Step #0 - copy current data into result
                result._data[k] = _data[k]; 
            }
                
            left = _data.Length - 2;  // Step #1 - Find left value 
            while ((result._data[left] > result._data[left+1]) && (left >= 1)) {
                --left;
            }

            if ((left == 0) && (_data[left] > _data[left+1]))
                return null;  

            right = _data.Length - 1;  // Step #2 - find right; first value > left
            while (result._data[left] > result._data[right]) {
                --right;
            }
                
            int temp = result._data[left];  // Step #3 - swap [left] and [right]
            result._data[left] = result._data[right];
            result._data[right] = temp;
                                
            int i = left + 1;              // Step #4 - order the tail
            int j = _data.Length - 1;  

            while (i < j) {
                temp = result._data[i];
                result._data[i++] = result._data[j];
                result._data[j--] = temp;
            }

            return result;
        }  // Successor()

        public object[] ApplyTo(object[] arr) {
            if (arr.Length != _data.Length)
                return null;

            object[] result = new object[arr.Length];
            for (int i = 0; i < result.Length; ++i) {
                result[i] = arr[_data[i]];
            }

            return result;
        }  // ApplyTo()

        public Permutation Inverse() {
            int[] inverse = new int[_data.Length];
                
            for (int i = 0; i < inverse.Length; ++i) {
                inverse[_data[i]] = i;
            }

            return new Permutation(inverse);
        }  // Inverse()

    }  // class Permutation 
}
